﻿public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution
{
    public TreeNode TrimBST(TreeNode root, int low, int high)
    {
        // 移动根节点
        while (root is not null)
        {
            if (root.val <= high && root.val >= low) break;

            if (root.val > high) root = root.left;
            else if (root.val < low) root = root.right;
        }

        if (root is null) return root;
        
        // 辅助指针
        TreeNode pre = root;
        TreeNode LeftNode = root.left, RightNode = root.right;
        
        // 处理左分支
        while (LeftNode is not null)
        {
            if (LeftNode.val >= low)
            {
                pre = LeftNode;
                LeftNode = LeftNode.left;
            }
            else
            {
                LeftNode = LeftNode.right;
                pre.left = LeftNode;
            }
            
        }
        
        // 处理右分支
        pre = root;
        while (RightNode is not null)
        {
            if (RightNode.val <= high)
            {
                pre = RightNode;
                RightNode = RightNode.right;
            }
            else
            {
                RightNode = RightNode.left;
                pre.right = RightNode;
            }
            
        }
        return root;
    }

    public static void Main(string[] args)
    {
        int?[] root =
        [
            28, 12, 45, 4, 24, 35, 47, 2, 9, 14, 25, 31, 42, 46, 48, 0, 3, 8, 11, 13, 20, null, 26, 30, 33, 41, 43,
            null, null, null, 49, null, 1, null, null, 7, null, 10, null, null, null, 17, 22, null, 27, 29, null, 32,
            34, 36, null, null, 44, null, null, null, null, 6, null, null, null, 16, 18, 21, 23, null, null, null, null,
            null, null, null, null, null, 37, null, null, 5, null, 15, null, null, 19, null, null, null, null, null, 40,
            null, null, null, null, null, null, 39, null, 38
        ];
        int low = 12, high = 22;

        TreeNode rootNode = CreatBinaryTree(root);

        Solution solution = new Solution();
        rootNode = solution.TrimBST(rootNode, low, high);

        LevelOrderTraversa(rootNode);
    }

    private static void LevelOrderTraversa(TreeNode rootNode)
    {
        Queue<TreeNode> queue = new Queue<TreeNode>();
        if (rootNode is not null) queue.Enqueue(rootNode);
        TreeNode node;

        while (queue.Count > 0)
        {
            node = queue.Dequeue();
            
            // 访问节点
            Console.Write($"{node.val} ");
            if (node.left is not null) queue.Enqueue(node.left);
            if (node.right is not null) queue.Enqueue(node.right);
        }
        
    }

    private static TreeNode CreatBinaryTree(int?[] root)
    {
        Queue<TreeNode> queue = new Queue<TreeNode>();
        if (root is null || root.Length == 0 || root[0] is null) return null;
        
        // 根节点进队
        TreeNode rootNode = new TreeNode(root[0].Value);
        queue.Enqueue(rootNode);
        TreeNode node;
        int i = 1;
        bool flag;
        while (queue.Count > 0)
        {
            flag = true;
            // 出队
            node = queue.Dequeue();
            if (root[i] is not null)
            {
                flag = false;
                node.left = new TreeNode(root[i].Value);
                queue.Enqueue(node.left);
            }
            
            if (++i >= root.Length) break;
            if (root[i] is not null)
            {
                flag = false;
                node.right = new TreeNode(root[i].Value);
                queue.Enqueue(node.right);
            }

            if (++i >= root.Length) break;
            if (flag)
            {
                queue.Enqueue(node);
            }
        }

        return rootNode;
    }
}